package Offer;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//幼儿园老师安排小朋友分组
public class makeFriend {
    public static int makeFrindGroupMin(Map<String, String> map) {
        /*思路：
         *      若2个小朋友均不在已知的所有组里，则创建新组；
         *      若1个小朋友不在已知的组里，则将其加入到另一个小朋友的组里
         *      若2个小朋友在不同的组里，则合并两组
         * */
        List<List> totalList = new ArrayList<>();
        for (Map.Entry<String, String> entry : map.entrySet()) {
            boolean aIsNot = true;
            boolean bIsNot = true;
            String a = entry.getKey();
            String b = entry.getValue();
            for (List<String> list : totalList) {
                if (list.contains(a)) {
                    aIsNot = false;
                    //a在 接下来判断b在不在
                    for (List<String> list2 : totalList) {
                        if (list2.contains(b)) {
                            //a在b在
                            bIsNot = false;
                            //判断a和b在不在同一个组
                            if (list2.contains(a)) {
                                //在同一个组，啥都不干就行了
                            } else {
                                //合并两个组
                                totalList.remove(list2);
                                while (!list2.isEmpty()) {
                                    list.add(list2.remove(0));
                                }
                            }
                            break;
                        }
                    }
                    //a在b不在
                    if (bIsNot) {
                        list.add(b);
                    }
                    break;
                }
            }
            if (aIsNot) {
                for (List<String> list : totalList) {
                    if (list.contains(b)) {
                        //a不在，b在
                        bIsNot = false;
                        list.add(a);
                        break;
                    }
                }
                if(bIsNot){
                    //a,b都不在，则新建一个组
                    List<String> newList = new ArrayList<String>();
                    newList.add(a);
                    newList.add(b);
                    totalList.add(newList);
                }
            }
        }
        return totalList.size();
    }

    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        map.put("Jack","Tom");
        map.put("Alice","John");
        map.put("Jessica","Leonie");
        map.put("Tom","Alice");
        map.put("John","Jack");
        map.put("Leonie","Jessica");
        System.out.println(makeFrindGroupMin(map));
    }
}
